<!DOCTYPE html>
<html lang="">
    <head><meta charset='utf-8'>
<meta name='viewport' content='width=device-width, initial-scale=1'>
<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js">
</script><meta name='description' content='前缀树 前缀树的概念 Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
前缀树的基本性质   根节点不包含字符，除根节点外每一个节点都只包含一个字符。
  从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
  每个节点的所有子节点包含的字符都不相同。 通过前缀树的性质，我们可以清楚的明白前缀树的根本是利用路径去表达某个单词是否在树中。
   
通过图片我们可以看到一条路径下是由多个字符所组成，那么想要在树中表示出某个单词，就需要对某个单词结束的字母进行一个标志。如下图：
 
代码实现 首先我们来分析一下树的节点构成：
class Node1 { public boolean end; public Node1[] nexts; public Node1() { end = false; nexts = new Node1[26];//代表26个字符  } } end：用于标识该节点是否是单词结束的节点
nexts：用于表示当前节点（字符）的下一个节点（字符）所在位置（要理解节点只是占位，路径才是存储）
(ps:还可以根据具体需求添加节点构成，例如：节点结束次数)
下面来看我们的整体代码：
class Trie { // 前缀树节点类型  class Node1 { public boolean end; public Node1[] nexts; public Node1() { end = false; nexts = new Node1[26]; } } private Node1 root; public Trie() { root = new Node1(); } //向前缀树中插入单词  public void insert(String word) { if(word==null){ return; } char[] chs = word.'><title>前缀树</title>

<link rel='canonical' href='http://example.org/post/%E5%89%8D%E7%BC%80%E6%A0%91/'>

<link rel="stylesheet" href="/scss/style.min.css"><meta property='og:title' content='前缀树'>
<meta property='og:description' content='前缀树 前缀树的概念 Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
前缀树的基本性质   根节点不包含字符，除根节点外每一个节点都只包含一个字符。
  从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
  每个节点的所有子节点包含的字符都不相同。 通过前缀树的性质，我们可以清楚的明白前缀树的根本是利用路径去表达某个单词是否在树中。
   
通过图片我们可以看到一条路径下是由多个字符所组成，那么想要在树中表示出某个单词，就需要对某个单词结束的字母进行一个标志。如下图：
 
代码实现 首先我们来分析一下树的节点构成：
class Node1 { public boolean end; public Node1[] nexts; public Node1() { end = false; nexts = new Node1[26];//代表26个字符  } } end：用于标识该节点是否是单词结束的节点
nexts：用于表示当前节点（字符）的下一个节点（字符）所在位置（要理解节点只是占位，路径才是存储）
(ps:还可以根据具体需求添加节点构成，例如：节点结束次数)
下面来看我们的整体代码：
class Trie { // 前缀树节点类型  class Node1 { public boolean end; public Node1[] nexts; public Node1() { end = false; nexts = new Node1[26]; } } private Node1 root; public Trie() { root = new Node1(); } //向前缀树中插入单词  public void insert(String word) { if(word==null){ return; } char[] chs = word.'>
<meta property='og:url' content='http://example.org/post/%E5%89%8D%E7%BC%80%E6%A0%91/'>
<meta property='og:site_name' content='我的技术小屋'>
<meta property='og:type' content='article'><meta property='article:section' content='Post' /><meta property='article:tag' content='前缀树' /><meta property='article:published_time' content='2021-12-28T00:00:00&#43;00:00'/><meta property='article:modified_time' content='2021-12-28T00:00:00&#43;00:00'/><meta property='og:image' content='http://example.org/post/%E5%89%8D%E7%BC%80%E6%A0%91/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84.png' />
<meta name="twitter:title" content="前缀树">
<meta name="twitter:description" content="前缀树 前缀树的概念 Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
前缀树的基本性质   根节点不包含字符，除根节点外每一个节点都只包含一个字符。
  从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
  每个节点的所有子节点包含的字符都不相同。 通过前缀树的性质，我们可以清楚的明白前缀树的根本是利用路径去表达某个单词是否在树中。
   
通过图片我们可以看到一条路径下是由多个字符所组成，那么想要在树中表示出某个单词，就需要对某个单词结束的字母进行一个标志。如下图：
 
代码实现 首先我们来分析一下树的节点构成：
class Node1 { public boolean end; public Node1[] nexts; public Node1() { end = false; nexts = new Node1[26];//代表26个字符  } } end：用于标识该节点是否是单词结束的节点
nexts：用于表示当前节点（字符）的下一个节点（字符）所在位置（要理解节点只是占位，路径才是存储）
(ps:还可以根据具体需求添加节点构成，例如：节点结束次数)
下面来看我们的整体代码：
class Trie { // 前缀树节点类型  class Node1 { public boolean end; public Node1[] nexts; public Node1() { end = false; nexts = new Node1[26]; } } private Node1 root; public Trie() { root = new Node1(); } //向前缀树中插入单词  public void insert(String word) { if(word==null){ return; } char[] chs = word."><meta name="twitter:card" content="summary_large_image">
    <meta name="twitter:image" content='http://example.org/post/%E5%89%8D%E7%BC%80%E6%A0%91/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84.png' />
    <link rel="shortcut icon" href="/img/%e7%bc%85%e5%9b%a0%e7%8c%ab.png" />
<style>
    :root {
        --article-font-family: "Noto Serif SC", var(--base-font-family);
    }
</style>

<script> 
		(function () {
		    const customFont = document.createElement('link');
		    customFont.href = "https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@300;700&display=swap"; 
		    customFont.type = "text/css";
		    customFont.rel = "stylesheet";
		
		    document.head.appendChild(customFont);
		}());
</script>
    </head>
    <body class="
    article-page has-toc
">
    <script>
        (function() {
            const colorSchemeKey = 'StackColorScheme';
            if(!localStorage.getItem(colorSchemeKey)){
                localStorage.setItem(colorSchemeKey, "auto");
            }
        })();
    </script><script>
    (function() {
        const colorSchemeKey = 'StackColorScheme';
        const colorSchemeItem = localStorage.getItem(colorSchemeKey);
        const supportDarkMode = window.matchMedia('(prefers-color-scheme: dark)').matches === true;

        if (colorSchemeItem == 'dark' || colorSchemeItem === 'auto' && supportDarkMode) {
            

            document.documentElement.dataset.scheme = 'dark';
        } else {
            document.documentElement.dataset.scheme = 'light';
        }
    })();
</script>
<div class="container main-container flex 
    
        extended
    
">
    
        <div id="article-toolbar">
            <a href="/" class="back-home">
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-chevron-left" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <polyline points="15 6 9 12 15 18" />
</svg>



                <span>Back</span>
            </a>
        </div>
    
<main class="main full-width">
    <article class="has-image main-article">
    <header class="article-header">
        <div class="article-image">
            <a href="/post/%E5%89%8D%E7%BC%80%E6%A0%91/">
                <img src="/post/%E5%89%8D%E7%BC%80%E6%A0%91/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_huc73353cd759cf331bc8f45f066092ff6_14396_800x0_resize_box_3.png"
                        srcset="/post/%E5%89%8D%E7%BC%80%E6%A0%91/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_huc73353cd759cf331bc8f45f066092ff6_14396_800x0_resize_box_3.png 800w, /post/%E5%89%8D%E7%BC%80%E6%A0%91/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_huc73353cd759cf331bc8f45f066092ff6_14396_1600x0_resize_box_3.png 1600w"
                        width="800" 
                        height="444" 
                        loading="lazy"
                        alt="Featured image of post 前缀树" />
                
            </a>
        </div>
    

    <div class="article-details">
    
    <header class="article-category">
        
            <a href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" >
                数据结构
            </a>
        
    </header>
    

    <h2 class="article-title">
        <a href="/post/%E5%89%8D%E7%BC%80%E6%A0%91/">前缀树</a>
    </h2>

    

    
    <footer class="article-time">
        
            <div>
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-calendar-time" width="56" height="56" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <path d="M11.795 21h-6.795a2 2 0 0 1 -2 -2v-12a2 2 0 0 1 2 -2h12a2 2 0 0 1 2 2v4" />
  <circle cx="18" cy="18" r="4" />
  <path d="M15 3v4" />
  <path d="M7 3v4" />
  <path d="M3 11h16" />
  <path d="M18 16.496v1.504l1 1" />
</svg>
                <time class="article-time--published">Dec 28, 2021</time>
            </div>
        

        
            <div>
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-clock" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="12" cy="12" r="9" />
  <polyline points="12 7 12 12 15 15" />
</svg>



                <time class="article-time--reading">
                    2 minute read
                </time>
            </div>
        
    </footer>
    
</div>
</header>

    <section class="article-content">
    <h1 id="前缀树">前缀树</h1>
<h2 id="前缀树的概念">前缀树的概念</h2>
<p>Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较。</p>
<p>Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。</p>
<h2 id="前缀树的基本性质">前缀树的基本性质</h2>
<ol>
<li>
<p>根节点不包含字符，除根节点外每一个节点都只包含一个字符。</p>
</li>
<li>
<p>从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。</p>
</li>
<li>
<p>每个节点的所有子节点包含的字符都不相同。
通过前缀树的性质，我们可以清楚的明白前缀树的根本是利用路径去表达某个单词是否在树中。</p>
</li>
</ol>
<p><figure 
	
		class="gallery-image" 
		style="
			flex-grow: 135; 
			flex-basis: 324px"
	>
	<a href="/post/%E5%89%8D%E7%BC%80%E6%A0%91/%E5%89%8D%E7%BC%80%E6%A0%91.png" data-size="536x397">
		<img src="/post/%E5%89%8D%E7%BC%80%E6%A0%91/%E5%89%8D%E7%BC%80%E6%A0%91.png"
			width="536"
			height="397"
			srcset="/post/%E5%89%8D%E7%BC%80%E6%A0%91/%E5%89%8D%E7%BC%80%E6%A0%91_hub18e15909f15af521f378ecff478d85e_26569_480x0_resize_box_3.png 480w, /post/%E5%89%8D%E7%BC%80%E6%A0%91/%E5%89%8D%E7%BC%80%E6%A0%91_hub18e15909f15af521f378ecff478d85e_26569_1024x0_resize_box_3.png 1024w"
			loading="lazy"
			>
	</a>
	
</figure></p>
<p>通过图片我们可以看到一条路径下是由多个字符所组成，那么想要在树中表示出某个单词，就需要对某个单词结束的字母进行一个标志。如下图：</p>
<p><figure 
	
		class="gallery-image" 
		style="
			flex-grow: 134; 
			flex-basis: 321px"
	>
	<a href="/post/%E5%89%8D%E7%BC%80%E6%A0%91/qianzhui2.png" data-size="536x400">
		<img src="/post/%E5%89%8D%E7%BC%80%E6%A0%91/qianzhui2.png"
			width="536"
			height="400"
			srcset="/post/%E5%89%8D%E7%BC%80%E6%A0%91/qianzhui2_hub18e15909f15af521f378ecff478d85e_31417_480x0_resize_box_3.png 480w, /post/%E5%89%8D%E7%BC%80%E6%A0%91/qianzhui2_hub18e15909f15af521f378ecff478d85e_31417_1024x0_resize_box_3.png 1024w"
			loading="lazy"
			>
	</a>
	
</figure></p>
<h2 id="代码实现">代码实现</h2>
<p>首先我们来分析一下树的节点构成：</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-java" data-lang="java">  <span style="color:#66d9ef">class</span> <span style="color:#a6e22e">Node1</span> <span style="color:#f92672">{</span>
        <span style="color:#66d9ef">public</span> <span style="color:#66d9ef">boolean</span> end<span style="color:#f92672">;</span>
        <span style="color:#66d9ef">public</span> Node1<span style="color:#f92672">[]</span> nexts<span style="color:#f92672">;</span>

        <span style="color:#66d9ef">public</span> <span style="color:#a6e22e">Node1</span><span style="color:#f92672">()</span> <span style="color:#f92672">{</span>
            end <span style="color:#f92672">=</span> <span style="color:#66d9ef">false</span><span style="color:#f92672">;</span>
            nexts <span style="color:#f92672">=</span> <span style="color:#66d9ef">new</span> Node1<span style="color:#f92672">[</span>26<span style="color:#f92672">];</span><span style="color:#75715e">//代表26个字符
</span><span style="color:#75715e"></span>        <span style="color:#f92672">}</span>
    <span style="color:#f92672">}</span>
</code></pre></div><p><strong>end</strong>：用于标识该节点是否是单词结束的节点</p>
<p><strong>nexts</strong>：用于表示当前节点（字符）的下一个节点（字符）所在位置（要理解节点只是占位，路径才是存储）</p>
<p>(<strong>ps</strong>:还可以根据具体需求添加节点构成，例如：节点结束次数)</p>
<p>下面来看我们的整体代码：</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-java" data-lang="java"><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">Trie</span> <span style="color:#f92672">{</span>
    <span style="color:#75715e">// 前缀树节点类型
</span><span style="color:#75715e"></span>    <span style="color:#66d9ef">class</span> <span style="color:#a6e22e">Node1</span> <span style="color:#f92672">{</span>
        <span style="color:#66d9ef">public</span> <span style="color:#66d9ef">boolean</span> end<span style="color:#f92672">;</span>
        <span style="color:#66d9ef">public</span> Node1<span style="color:#f92672">[]</span> nexts<span style="color:#f92672">;</span>

        <span style="color:#66d9ef">public</span> <span style="color:#a6e22e">Node1</span><span style="color:#f92672">()</span> <span style="color:#f92672">{</span>
            end <span style="color:#f92672">=</span> <span style="color:#66d9ef">false</span><span style="color:#f92672">;</span>
            nexts <span style="color:#f92672">=</span> <span style="color:#66d9ef">new</span> Node1<span style="color:#f92672">[</span>26<span style="color:#f92672">];</span>
        <span style="color:#f92672">}</span>
    <span style="color:#f92672">}</span>
    <span style="color:#66d9ef">private</span> Node1 root<span style="color:#f92672">;</span>
    <span style="color:#66d9ef">public</span> <span style="color:#a6e22e">Trie</span><span style="color:#f92672">()</span> <span style="color:#f92672">{</span>
        root <span style="color:#f92672">=</span> <span style="color:#66d9ef">new</span> Node1<span style="color:#f92672">();</span>
    <span style="color:#f92672">}</span>

    <span style="color:#75715e">//向前缀树中插入单词
</span><span style="color:#75715e"></span>    <span style="color:#66d9ef">public</span> <span style="color:#66d9ef">void</span> <span style="color:#a6e22e">insert</span><span style="color:#f92672">(</span>String word<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
        <span style="color:#66d9ef">if</span><span style="color:#f92672">(</span>word<span style="color:#f92672">==</span><span style="color:#66d9ef">null</span><span style="color:#f92672">){</span>
            <span style="color:#66d9ef">return</span><span style="color:#f92672">;</span>
        <span style="color:#f92672">}</span>
        <span style="color:#66d9ef">char</span><span style="color:#f92672">[]</span> chs <span style="color:#f92672">=</span> word<span style="color:#f92672">.</span><span style="color:#a6e22e">toCharArray</span><span style="color:#f92672">();</span>
        Node1 node <span style="color:#f92672">=</span> root<span style="color:#f92672">;</span>
        <span style="color:#66d9ef">int</span> index <span style="color:#f92672">=</span> 0<span style="color:#f92672">;</span>
        <span style="color:#75715e">//遍历字符串由字符对应节点数组的某个位置形成一条路径
</span><span style="color:#75715e"></span>        <span style="color:#66d9ef">for</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> i <span style="color:#f92672">=</span> 0<span style="color:#f92672">;</span> i <span style="color:#f92672">&lt;</span> chs<span style="color:#f92672">.</span><span style="color:#a6e22e">length</span><span style="color:#f92672">;</span> i<span style="color:#f92672">++)</span> <span style="color:#f92672">{</span>
            <span style="color:#75715e">// 由字符，对应成走向哪条路
</span><span style="color:#75715e"></span>            index <span style="color:#f92672">=</span> chs<span style="color:#f92672">[</span>i<span style="color:#f92672">]</span> <span style="color:#f92672">-</span> <span style="color:#e6db74">&#39;a&#39;</span><span style="color:#f92672">;</span>
            <span style="color:#75715e">//当前节点的next数组中该位置为空的话
</span><span style="color:#75715e"></span>            <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>node<span style="color:#f92672">.</span><span style="color:#a6e22e">nexts</span><span style="color:#f92672">[</span>index<span style="color:#f92672">]</span> <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
                <span style="color:#75715e">//生成节点占位
</span><span style="color:#75715e"></span>                node<span style="color:#f92672">.</span><span style="color:#a6e22e">nexts</span><span style="color:#f92672">[</span>index<span style="color:#f92672">]</span> <span style="color:#f92672">=</span> <span style="color:#66d9ef">new</span> Node1<span style="color:#f92672">();</span>
            <span style="color:#f92672">}</span>
            node <span style="color:#f92672">=</span> node<span style="color:#f92672">.</span><span style="color:#a6e22e">nexts</span><span style="color:#f92672">[</span>index<span style="color:#f92672">];</span>
        <span style="color:#f92672">}</span>
        node<span style="color:#f92672">.</span><span style="color:#a6e22e">end</span><span style="color:#f92672">=</span><span style="color:#66d9ef">true</span><span style="color:#f92672">;</span>
    <span style="color:#f92672">}</span>

    <span style="color:#75715e">//判断前缀树中是否有某个单词
</span><span style="color:#75715e"></span>    <span style="color:#66d9ef">public</span> <span style="color:#66d9ef">boolean</span> <span style="color:#a6e22e">search</span><span style="color:#f92672">(</span>String word<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
        <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>word <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
            <span style="color:#66d9ef">return</span> <span style="color:#66d9ef">false</span><span style="color:#f92672">;</span>
        <span style="color:#f92672">}</span>
        <span style="color:#66d9ef">char</span><span style="color:#f92672">[]</span> chs <span style="color:#f92672">=</span> word<span style="color:#f92672">.</span><span style="color:#a6e22e">toCharArray</span><span style="color:#f92672">();</span>
        Node1 node <span style="color:#f92672">=</span> root<span style="color:#f92672">;</span>
        <span style="color:#66d9ef">int</span> index <span style="color:#f92672">=</span> 0<span style="color:#f92672">;</span>
        <span style="color:#66d9ef">for</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> i <span style="color:#f92672">=</span> 0<span style="color:#f92672">;</span> i <span style="color:#f92672">&lt;</span> chs<span style="color:#f92672">.</span><span style="color:#a6e22e">length</span><span style="color:#f92672">;</span> i<span style="color:#f92672">++)</span> <span style="color:#f92672">{</span>
            <span style="color:#75715e">// 由字符，对应成走向哪条路
</span><span style="color:#75715e"></span>            index <span style="color:#f92672">=</span> chs<span style="color:#f92672">[</span>i<span style="color:#f92672">]</span> <span style="color:#f92672">-</span> <span style="color:#e6db74">&#39;a&#39;</span><span style="color:#f92672">;</span>
            <span style="color:#75715e">//当前节点的next数组中该位置为空，表示当前树对应路径中无该字符
</span><span style="color:#75715e"></span>            <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>node<span style="color:#f92672">.</span><span style="color:#a6e22e">nexts</span><span style="color:#f92672">[</span>index<span style="color:#f92672">]</span> <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
                <span style="color:#66d9ef">return</span> <span style="color:#66d9ef">false</span><span style="color:#f92672">;</span>
            <span style="color:#f92672">}</span>
            <span style="color:#75715e">//继续往下走
</span><span style="color:#75715e"></span>            node <span style="color:#f92672">=</span> node<span style="color:#f92672">.</span><span style="color:#a6e22e">nexts</span><span style="color:#f92672">[</span>index<span style="color:#f92672">];</span>
        <span style="color:#f92672">}</span>
        <span style="color:#66d9ef">return</span> node<span style="color:#f92672">.</span><span style="color:#a6e22e">end</span><span style="color:#f92672">;</span>
    <span style="color:#f92672">}</span>

    <span style="color:#75715e">//判断前缀树中是否有前缀
</span><span style="color:#75715e"></span>    <span style="color:#66d9ef">public</span> <span style="color:#66d9ef">boolean</span> <span style="color:#a6e22e">startsWith</span><span style="color:#f92672">(</span>String prefix<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
        <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>prefix <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
            <span style="color:#66d9ef">return</span> <span style="color:#66d9ef">false</span><span style="color:#f92672">;</span>
        <span style="color:#f92672">}</span>
        <span style="color:#66d9ef">char</span><span style="color:#f92672">[]</span> chs <span style="color:#f92672">=</span> prefix<span style="color:#f92672">.</span><span style="color:#a6e22e">toCharArray</span><span style="color:#f92672">();</span>
        Node1 node <span style="color:#f92672">=</span> root<span style="color:#f92672">;</span>
        <span style="color:#66d9ef">int</span> index <span style="color:#f92672">=</span> 0<span style="color:#f92672">;</span>
        <span style="color:#66d9ef">for</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> i <span style="color:#f92672">=</span> 0<span style="color:#f92672">;</span> i <span style="color:#f92672">&lt;</span> chs<span style="color:#f92672">.</span><span style="color:#a6e22e">length</span><span style="color:#f92672">;</span> i<span style="color:#f92672">++)</span> <span style="color:#f92672">{</span>
            index <span style="color:#f92672">=</span> chs<span style="color:#f92672">[</span>i<span style="color:#f92672">]</span> <span style="color:#f92672">-</span> <span style="color:#e6db74">&#39;a&#39;</span><span style="color:#f92672">;</span>
            <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>node<span style="color:#f92672">.</span><span style="color:#a6e22e">nexts</span><span style="color:#f92672">[</span>index<span style="color:#f92672">]</span> <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
                <span style="color:#66d9ef">return</span> <span style="color:#66d9ef">false</span><span style="color:#f92672">;</span>
            <span style="color:#f92672">}</span>
            node <span style="color:#f92672">=</span> node<span style="color:#f92672">.</span><span style="color:#a6e22e">nexts</span><span style="color:#f92672">[</span>index<span style="color:#f92672">];</span>
        <span style="color:#f92672">}</span>
        <span style="color:#66d9ef">return</span> <span style="color:#66d9ef">true</span><span style="color:#f92672">;</span>
    <span style="color:#f92672">}</span>
<span style="color:#f92672">}</span>

</code></pre></div><p><strong>ps：想了解前缀树更多应用题目，可以在博客中通过前缀树标签查阅</strong></p>

</section>


    <footer class="article-footer">
    
    <section class="article-tags">
        
            <a href="/tags/%E5%89%8D%E7%BC%80%E6%A0%91/">前缀树</a>
        
    </section>


    </footer>


    
</article>

    <aside class="related-contents--wrapper">
    
    
        <h2 class="section-title">Related contents</h2>
        <div class="related-contents">
            <div class="flex article-list--tile">
                
                    
<article class="has-image">
    <a href="/post/%E8%BF%9E%E6%8E%A5%E8%AF%8D/">
        
        
            <div class="article-image">
                <img src="/post/%E8%BF%9E%E6%8E%A5%E8%AF%8D/aa.a45d3121559bf91a625b526f9ecf19e6_hud3c20fccaaa9a9c72056f364d14b5f1f_1074620_250x150_fill_box_smart1_3.png" 
                        width="250" 
                        height="150" 
                        loading="lazy" 
                        data-key="连接词" 
                        data-hash="md5-pF0xIVWb&#43;RpiW1Jvns8Z5g==">
                
            </div>
        

        <div class="article-details">
            <h2 class="article-title">连接词</h2>
        </div>
    </a>
</article>
                
            </div>
        </div>
    
</aside>

     
    
        
    

    <script src="https://s3.pstatp.com/cdn/expire-1-M/jquery/3.2.1/jquery.min.js"></script>
        <script>
        function color_tags() {
            var colorArr = ["#428BCA", "#AEDCAE", "#ECA9A7", "#DA99FF", "#FFB380", "#D9B999"];
            $('.tagCloud-tags a').each(function () {
                try {
                    tagsColor = colorArr[Math.floor(Math.random() * colorArr.length)];
                    $(this).css("background", tagsColor); 
                }
                catch (err) { }
            });
        }

        $(document).ready(function () {
            color_tags()
        });
    </script>
    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

<footer class="site-footer">
<span id="busuanzi_container_site_uv">
    本站总访问量<span id="busuanzi_value_site_uv"></span>次
</span>
    <section class="copyright">
        &copy; 
        
        2022zp妙妙屋·<i class="fas fa-bell"></i> <a id="days">0</a>Days<br>共叭叭了 3682字·共 16篇文章</br><span><p>
    </section>
    <div style="width:300px;margin:0 auto; padding:20px 0;">
    <a href="https://beian.miit.gov.cn/，" rel="external nofollow" target="_blank"><p style="float:left;height:20px;line-height:20px;margin: 0px 0px 0px 25px; color:#939393;">京ICP备2022000201号-1</p></a></span>
		 		<a target="_blank" href="http://www.beian.gov.cn/portal/registerSystemInfo?recordcode=11011102001825" style="display:inline-block;text-decoration:none;height:20px;line-height:20px;"><img src="/beian.png" style="float:left;"/><p style="float:left;height:20px;line-height:20px;margin: 0px 0px 0px 5px; color:#939393;">京公网安备 11011102001825号</p></a>
	</div>
    <section class="powerby">
        Built with <a href="https://gohugo.io/" target="_blank" rel="noopener">Hugo</a> <br />
        Theme <b><a href="https://github.com/CaiJimmy/hugo-theme-stack" target="_blank" rel="noopener" data-version="3.5.0">Stack</a></b> designed by <a href="www.zpzp.vip" target="_blank" rel="noopener">ZP</a>
    </section>
</footer>



    
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

    
    <div class="pswp__bg"></div>

    
    <div class="pswp__scroll-wrap">

        
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>

        
        <div class="pswp__ui pswp__ui--hidden">

            <div class="pswp__top-bar">

                

                <div class="pswp__counter"></div>

                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>

                <button class="pswp__button pswp__button--share" title="Share"></button>

                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>

                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>

                
                
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                        <div class="pswp__preloader__cut">
                            <div class="pswp__preloader__donut"></div>
                        </div>
                    </div>
                </div>
            </div>

            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div>
            </div>

            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>

            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>

            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>

        </div>

    </div>

</div><script 
                src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.js"integrity="sha256-ePwmChbbvXbsO02lbM3HoHbSHTHFAeChekF1xKJdleo="crossorigin="anonymous"
                defer="true"
                >
            </script><script 
                src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe-ui-default.min.js"integrity="sha256-UKkzOn/w1mBxRmLLGrSeyB4e1xbrp4xylgAWb3M42pU="crossorigin="anonymous"
                defer="true"
                >
            </script><link 
                rel="stylesheet" 
                href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/default-skin/default-skin.css"integrity="sha256-c0uckgykQ9v5k&#43;IqViZOZKc47Jn7KQil4/MP3ySA3F8="crossorigin="anonymous"
            ><link 
                rel="stylesheet" 
                href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.css"integrity="sha256-SBLU4vv6CA6lHsZ1XyTdhyjJxCjPif/TRkjnsyGAGnE="crossorigin="anonymous"
            >

            </main>
    
        <aside class="sidebar right-sidebar sticky">
            <section class="widget archives">
                <div class="widget-icon">
                    <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-hash" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <line x1="5" y1="9" x2="19" y2="9" />
  <line x1="5" y1="15" x2="19" y2="15" />
  <line x1="11" y1="4" x2="7" y2="20" />
  <line x1="17" y1="4" x2="13" y2="20" />
</svg>



                </div>
                <h2 class="widget-title section-title">Table of contents</h2>
                
                <div class="widget--toc">
                    <nav id="TableOfContents">
  <ul>
    <li><a href="#前缀树的概念">前缀树的概念</a></li>
    <li><a href="#前缀树的基本性质">前缀树的基本性质</a></li>
    <li><a href="#代码实现">代码实现</a></li>
  </ul>
</nav>
                </div>
            </section>
        </aside>
    

        </div>
        <script 
                src="https://cdn.jsdelivr.net/npm/node-vibrant@3.1.5/dist/vibrant.min.js"integrity="sha256-5NovOZc4iwiAWTYIFiIM7DxKUXKWvpVEuMEPLzcm5/g="crossorigin="anonymous"
                defer="false"
                >
            </script><script type="text/javascript" src="/ts/main.js" defer></script>
<script>
    (function () {
        const customFont = document.createElement('link');
        customFont.href = "https://fonts.googleapis.com/css2?family=Lato:wght@300;400;700&display=swap";

        customFont.type = "text/css";
        customFont.rel = "stylesheet";

        document.head.appendChild(customFont);
    }());
</script>

<script
    src="https://cdn.jsdelivr.net/gh/zhixuan2333/gh-blog@v0.1.0/js/ribbon.min.js"
    integrity="sha384-UEK8ZiP3VgFNP8KnKMKDmd4pAUAOJ59Y2Jo3ED2Z5qKQf6HLHovMxq7Beb9CLPUe"
    crossorigin="anonymous"
    size="300"
    alpha="0.6"
    zindex="-1"
    defer
></script>
<script
    src="https://cdn.jsdelivr.net/gh/zhixuan2333/gh-blog@v0.1.0/js/nprogress.min.js"
    integrity="sha384-bHDlAEUFxsRI7JfULv3DTpL2IXbbgn4JHQJibgo5iiXSK6Iu8muwqHANhun74Cqg"
    crossorigin="anonymous"
></script>
<link
    rel="stylesheet"
    href="https://cdn.jsdelivr.net/gh/zhixuan2333/gh-blog@v0.1.0/css/nprogress.css"
    integrity="sha384-KJyhr2syt5+4M9Pz5dipCvTrtvOmLk/olWVdfhAp858UCa64Ia5GFpTN7+G4BWpE"
    crossorigin="anonymous"
/>
<script src="/js/snow.js"></script>
<script>
    NProgress.start();
    document.addEventListener("readystatechange", () => {
        if (document.readyState === "interactive") NProgress.inc(0.8);
        if (document.readyState === "complete") NProgress.done();
    });
</script>

    </body>
</html>
